前言

講解完二元搜尋樹的定義、特性以及 Build & delete 操作，將要談 BST 的各種其他操作之演算法，例如 Search for x, Insert x, Find ith small elememt，在這些演算法中，會使用 Recursive 的觀念，所以必須要事先了解一下遞迴怎麼運作，才能比較清楚的理解唷

BST 之各種操作

令 Node 的結構為 leftlink data rightlink，執行以下操作

Search for x

search(t,x){   // search x from tree(t)
    if( t is not nil ){
        if( x > t->data ) return search( t->rightlink , x ); // 往右子點尋找
        else if( x < t->data ) return search( t->leftlink , x ); // 往左子點尋找
        else return true; 
    }
    return false;
}

補充：在搜尋的時候，最糟糕的狀況就是欲搜尋的點是葉節點，因此 Worst case : O(logn) 即最小樹高

Insert X in BST

insert(t,x){
    if(t == null) return new_node(t); // 如果整棵樹為空，生成一新 Node
    else{
        if( x > t->data ) return insert( t->rightlink , x );
        if( x < t->data ) reutrn insert( t->leftchild , x );
    }
    return t;
}

補充：在插入的時候，同搜尋 Worst case : O(logn) 即最小樹高

Find ith Small elememt

原先的 Node 必須創造出一個新欄位 (Lsize)，代表左子樹node的數量，若以建立好便可執行以下 algo

search(t,i){
	if(t is not null){
		k = t->Lsize + 1; // 即 t 點為第 k (即左子樹數量+1)小
        // e.g 令一 node 左子樹有 2 個點，依照 BST 的定義，則該點就是整棵 BST 第 3 個小
		if( i == k ) return t->data;
		else if( i<k ) return search( t->lchild , i ); // 往左子樹找第 i 小
		else return search( t->rchild , i-k ); // 往右子樹找的話，代表他是右子樹的第 i-k 小
	}
}